De-duplicating storage systems, such as EMC® Data Domain® storage systems, employ a “segment index” to keep track of data segments that have already been stored. For each segment that has been stored, a fingerprint (e.g., hash) may be used to create an index entry that represents the segment and indicates a location in which the segment has been stored, e.g., a specific container or other logical structure or set of segment data. If a subsequently received segment is the same as a segment that has already been stored, a reference to the segment as stored previously may be provided and/or used, instead of storing the same segment again.
A segment index may be stored on disk, e.g., striped across a set of n disks. Performing a query against such an index may require random access input/output (I/O) operations with respect to the drive(s) on which the segment index are stored. As de-duplicating storage systems become larger and larger in scale, and as hard disk drives become increasing dense, the cost of such I/O operations may increase.